#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<string.h>
void MergeSort(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;

	MergeSort(arr, begin, mid, tmp);
	MergeSort(arr, mid + 1, end, tmp);

	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if(arr[begin1] <= arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}

	while (begin1 <= end1)
		tmp[i++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[i++] = arr[begin2++];

	memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
int main()
{
	int arr[10] = { 10,9,7,8,6,5,4,3,2,1 };
	int tmp[10] = { 0 };
	MergeSort(arr, 0, 9, tmp);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}